1. Field of the Invention
The present invention relates to a method and apparatus for performing division of two binary numbers in a digital system. The division may be performed using a microprocessor (μP), a microcomputer (μC), a Digital Signal Processor (DSP) or other similar digital processing device. The term Micro Computer Unit (MCU) will be used throughout this description to refer to any or all such processing devices.
2. Description of the Related Art
MCUs are typically used in a variety of devices requiring some form of digital processing capacity. Such devices cover a diverse range of uses ranging from washing machines to industrial control equipment, and televisions to central heating thermostats. A particular application for MCUs is in the field of telecommunications. MCUs are to be found in portable telephones and the associated base stations which allow the telephones to communicate with other users via a communication network.
MCUs used in telecommunication equipment are frequently employed to implement certain algorithms which are used e.g. to enhance the transmission of data, to encrypt data or to process control signals used to set up and control a communication channel. These algorithms are often carefully chosen so that they can be implemented in a straightforward fashion using existing MCUs.
In particular, prior art MCUs are generally not able to perform division operations particularly efficiently. Simple addition, subtraction and multiplication operations may be able to be performed in single instruction cycles, whereas division operations may occupy the MCU for many cycles. As such, algorithms are chosen or devised so that division is limited as far as possible to division by a factor of 2n only, which equates to a simple bit-shift operation.
MCUs which are capable of performing division operations in a relatively short number of clock cycles, or even a single clock cycle, require the provision of very many custom logic gates to perform this function. As such, the overall complexity of the MCU is increased along with its size and power consumption. This is particularly undesirable in handheld communication equipment where physical size and battery life are two important design factors.
Given integer numbers Numerator (N) and Denominator (D), the prior art teaches a number of different ways to perform the divide operation N/D. A first simple method is to repeatedly subtract D from N, noting the number of times this process is repeated in a counter Y. The number of times this is possible before N becomes less than D gives the integer value of the result in Y. The remainder is held in N. Of course, such a simplistic system can require many clock cycles if N is many times larger than D, and as such is unsuitable for all but the simplest and least speed-critical of systems.
A particular problem arises when trying to configure an MCU for use with the UTRA (Universal Terrestrial Radio Access) FDD (Frequency Division Duplex) W-CDMA (Wideband—Code Division Multiple Access) communication standard. This particular standard specifies a particular division operation for use in calculating the parameters for rate matching/puncturing in the channel coder rate matching algorithm.
In designing a custom MCU for use with the UTRA FDD W-CDMA standard, it is not expected that the division operation will be called by the algorithm so frequently that it will require a specific block of custom hardware to perform a division in one clock cycle, but on the other hand, a balance must be struck between complex custom hardware and an over-lengthy division process occupying too much MCU time.